本文是 Crafting a compiler ch4: Parsers and Recognizers 的筆記。

建議讀者：對於 CFG, terminal, nonterminal, production 有一些認識的人，以及正在看本書第四章的人。
本文目標：說明一些我個人對於一些詞的理解如 terminal alphabet, nonterminal alphabet, start symbol, vocabulary, derivation, sentential form, phrase, handle, regular grammar, BNF, recongnizer, LL parser, LR parser, set, list, iterator, first set, follow set, 我並不會注重在這些詞的定義，而是注重在我個人的解釋。

G = (N, Σ, P, S)

一個 grammer 可以表示為 G = (N, Σ, P, S), 其中

• G (grammer)：代表語法
• N 代表 non terminal
• Σ 代表 terminal
• p 代表 production
• S 代表 start symbol
• derivate: 使用了一個 production(rewriting rule)
• L(G): 實際上所有可能的程式碼的集合

一些取名慣例：

• 大寫開頭：nonterminal

• 小寫開頭或標點符號：terminal

• X, Y 開頭：terminal 以及 nonterminal 的集合

• 希臘字母：數個 terminal 以及 nonterminal, 但不一定可以從 start symbol derivate 而來

• sentential form：可以想成是從 S(start symbol) derivate 到一半的 string

• leftmost derivation: 從最左邊的 nonterminal 開始 derivation

• rightmost derivation(canonical derivation): 從最右邊的 nonterminal 開始 derivation

• Backus-Naur form(BNF)：多加了一些功能的 CFG，以一個 production 為例子：
  Declaration → [ final ] [ static ] [ const ] Type identifier { , identifier }
  中括號內的可有可無，大括號內的可以重複數次。

First( α) = { a ∈ Σ | α ⇒* a β }
Follow( A ) = { b ∈ Σ | S ⇒+ α A b β }